#include <bits/stdc++.h>
using namespace std;

const int R = 5e5 + 10;
struct Node
{
	int son[2], l, r, lmax, rmax, maxv, tot;
} t[R * 2];
#define lc(k) t[k].son[0]
#define rc(k) t[k].son[1]
int a[R], root, tot;
void pushup(int k)
{
	t[k].lmax = max(t[lc(k)].lmax, t[lc(k)].tot + t[rc(k)].lmax);
	t[k].rmax = max(t[rc(k)].rmax, t[lc(k)].rmax + t[rc(k)].tot);
	t[k].maxv = max(max(t[lc(k)].maxv, t[rc(k)].maxv), t[lc(k)].rmax + t[rc(k)].lmax);
	t[k].tot = t[lc(k)].tot + t[rc(k)].tot;
}
void build(int &k, int l, int r)
{
	k = ++tot;
	t[k].l = l, t[k].r = r;
	if (l == r)
	{
		t[k].lmax = t[k].rmax = t[k].maxv = t[k].tot = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lc(k), l, mid);
	build(rc(k), mid + 1, r);
	pushup(k);
}
void update(int k, int p, int v)
{
	if (t[k].l == t[k].r)
	{
		t[k].lmax = t[k].rmax = t[k].maxv = t[k].tot = v;
		return;
	}
	int mid = (t[k].l + t[k].r) >> 1;
	if (p <= mid)
		update(lc(k), p, v);
	else
		update(rc(k), p, v);
	pushup(k);
}
Node query(int k, int x, int y)
{
	if (x <= t[k].l && y >= t[k].r)
	{
		return t[k];
	}
	int mid = (t[k].l + t[k].r) >> 1;
	if (y <= mid)
	{
		return query(lc(k), x, y);
	}
	else if (x > mid)
	{
		return query(rc(k), x, y);
	}
	else
	{
		Node lres = query(lc(k), x, y),
			 rres = query(rc(k), x, y),
			 res;
		res.lmax = max(lres.lmax, lres.tot + rres.lmax);
		res.rmax = max(rres.rmax, lres.rmax + rres.tot);
		res.maxv = max(max(lres.maxv, rres.maxv), lres.rmax + rres.lmax);
		res.tot = lres.tot + rres.tot;
		return res;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, k, l, r, p, v;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
	}
	build(root, 1, n);
	while (m--)
	{
		cin >> k;
		if (k == 1)
		{
			cin >> l >> r;
			if (l > r)
				swap(l, r);
			cout << query(root, l, r).maxv << '\n';
		}
		else
		{
			cin >> p >> v;
			update(root, p, v);
		}
	}
	return 0;
}
